An integrated circuit (IC) comprises cells of similar and/or various sizes, and connections between the cells. A cell includes several pins interconnected by wires to pins of one or more other cells. A net includes a set of pins connected by wires in order to form connections between the pins. A set of nets, called a netlist, defines the connections of an IC.
A router reads in the netlist of an IC, then generates wires, interconnecting pins of nets in the netlist. Once the nets in the netlist are connected, the IC will function correctly. However, due to the large number of nets in the netlist, it typically takes a long time for conventional routers to finish the connection task. In addition, the connections may be too numerous and/or overcrowded, such that conventional routers fail to finish the routing, particularly generating interconnections, without creating one or more design rule violations.
Many of these problems result from the strict adherence of routers to a grid representation of nodes with a uniform structure from layer to layer, and from routing the entire IC design at the same time. Such routers demand excessive amounts of memory and/or take a very long time to route the IC design.